package codetop.microsoft.T301;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: 18362
 * @Create: 2022-08-16 15:57:15 星期二
 */
class Solution {
    private Set<String> result = new HashSet<>();
    private int minNum = Integer.MAX_VALUE;
    private int maxSum;

    public List<String> removeInvalidParentheses(String s) {
        int left = 0, right = 0;
        for (int i=0; i<s.length(); ++i) {
            if (s.charAt(i) == '(')
                left++;
            else if (s.charAt(i) == ')')
                right++;
        }
        maxSum = Math.min(left, right);
        dfs(s, 0, 0, new StringBuilder());
        return new ArrayList<>(result);
    }

    private void dfs(String s, int cur, int sum, StringBuilder sb) {
        if (cur == s.length()) {
            if (sum == 0) {
                int num = s.length() - sb.length();
                if (num < minNum) {
                    result.clear();
                    result.add(sb.toString());
                    minNum = num;
                } else if (num == minNum)
                    result.add(sb.toString());
            }
            return;
        }
        if (cur - sb.length() > minNum)
            return;
        char c = s.charAt(cur);
        if (c >= 'a' && c <= 'z') {
            sb.append(c);
            dfs(s, cur+1, sum, sb);
            sb.deleteCharAt(sb.length()-1);
        } else if (c == '(') {
            if (sum + 1 <= maxSum) {
                sb.append(c);
                dfs(s, cur+1, sum+1, sb);
                sb.deleteCharAt(sb.length()-1);
            }
            dfs(s, cur+1, sum, sb);
        } else {
            if (sum - 1 >= 0) {
                sb.append(c);
                dfs(s, cur+1, sum-1, sb);
                sb.deleteCharAt(sb.length()-1);
            }
            dfs(s, cur+1, sum, sb);
        }
    }
}